\chapter{High-Level Synthesis}\label{CH::HLS}
\markboth {Chapter \ref{CH::HLS}. High-Level Synthesis}{}

The term \emph{Synthesis} is used in many fields, usually to mean a process which combines two or more pre-existing elements and results in something new. In terms of embedded systems, synthesis is the generation of a circuit model, starting from a less detailed one.

\vspace{1em} \noindent
Models can be classified into three main levels of abstraction, namely: \textit{architectural}, \textit{logic} and \textit{geometrical}. At the \textit{architectural level} a circuit
performs a set of operations, such as data computation or transfer. At the \textit{logic level},
a digital circuit evaluates a set of logic functions. At the \textit{geometrical level}, a circuit
is a set of geometrical entities.
\begin{figure}[htb]
\centering
\includegraphics[height=0.6\columnwidth]{./chapters/hls/images/design_flow.JPG}
\caption{Synthesis flow from behavioral specification to physical design}\label{fig:flow}
\end{figure}

\vspace{1em} \noindent
The model classification relates to a taxonomy of the synthesis tasks (see Figure~\ref{fig:flow}). These tasks are described in detail below, in the order that corresponds to their use in a top-down synthesis system.

\begin{itemize}
\item The \textit{architectural-level synthesis} corresponds to determining an assignment of the circuit functions to operators, called resources, as well as their interconnection and the timing of their execution. It has also been called \textit{high-level synthesis} or \textit{structural synthesis}, because it determines the macroscopic (i.e., block-level) structure of the circuit. A behavioral architectural-level model can be abstracted as a set of operations and dependencies. Architectural synthesis entails identifying the hardware resources that can implement the operations, scheduling the execution time of the operations and binding them to the resources. In other words, synthesis defines a structural model of a data path, as an interconnection of resources, and a logic-level model of a control unit, that issues the control signals to the data path according to the schedule. The macroscopic figures of merit of the implementation, such as circuit area and performance, depend heavily on this step. Indeed, architectural synthesis determines the degree of parallelism of the operations, so optimization at this level is very important.
\item After the architectural-level synthesis, the \textit{logic-level synthesis} step has to be performed. Logic-level synthesis is the manipulation of logic specifications to create logic models as an interconnection of logic primitives. Thus logic synthesis determines the microscopic (i.e., gate-level) structure of a circuit. The task of transforming a
logic model into an interconnection of instances of library cells, i.e., the back end
of logic synthesis, is often referred to as library binding or technology mapping.
A logic-level model of a circuit can be provided by a state transition diagram of a finite-state machine, by a circuit schematic or equivalently by an HDL model. It may be specified by a designer or synthesized from an architectural-level model.
The logic synthesis tasks may be different according to the nature of the circuit
(e.g., sequential or combinational) and to the initial representation (e.g., state diagram
or schematic). Since there are many possible configurations of a circuit, optimization plays
a major role, in connection with synthesis, in determining the microscopic figures
of merit of the implementation. The final outcome of logic synthesis is a fully structural representation, such as a gate-level netlist.
\item The final step is the \textit{geometrical-level synthesis}, that entails the specification of all geometric patterns defining the physical layout of the chip, as well as their position. It is often called \emph{physical design}. The layers of the layout are in correspondence with the masks used for chip fabrication.
Therefore, the geometrical layout is the final target of microelectronic circuit design.
Physical design depends much on the design style. On one end of the spectrum, for
custom design, physical design is handcrafted by using layout editors. This means
that the designer renounces the use of automated synthesis tools in the search for
optimizing the circuit geometries by fine hand-tuning. On the opposite end of the
spectrum, in case of prewired circuits, physical design is performed in a virtual
fashion, because chips are fully manufactured in advance.
The major tasks in physical design are placement and wiring, called also routing. Cell generation is essential in the particular case of macro-cell design, where cells are synthesized and not extracted from a library.
\end{itemize}
Circuit optimization is often performed in conjunction with synthesis. Optimization is motivated not only by the desire of maximizing the circuit quality, but also by the fact that synthesis without optimization would yield noncompetitive circuits at all, and therefore its value would be marginal.

\vspace{1em} \noindent
This thesis will present the entire high-level synthesis flow, describing in detail all steps executed by the synthesis, from the inputs given to the outputs obtained. In particular, this thesis would focus on two kinds of circuit optimizations performed during the flow, \emph{speculative execution} and \emph{storage module reduction}:
\begin{itemize}
  \item \textbf{Speculative code transformations} on mixed control-data flow design aim to reduce the length of the resulting schedules;
  \item \textbf{Register allocation and binding techniques} in high-level synthesis aim to minimize the storage requirements of circuits by sharing variables among registers and thus to minimize the required number of registers for a specific design. SSA-based intermediate representation would help to have a simpler liveness analysis and then to achieve an effective register allocation.
\end{itemize}

\vspace{1em} \noindent
The remaining of this Chapter is organized as follows. The high-level synthesis problem will be analyzed and described in detail in Section \ref{hls:overview}; HLS inputs, tasks and outputs are introduced and summarized in Sections \ref{hls:inputs}, \ref{hls:tasks} and \ref{hls:outputs}; main thesis objectives are described in Section \ref{hls:obj} and conclusions are proposed in last Section \ref{hls:concl}.

\section{Overview}\label{hls:overview}
\emph{High-Level Synthesis (HLS)} means constructing the macroscopic structure of a digital circuit, starting from behavioral models that can be captured by data-flow or sequencing graphs.
In detail, High-Level Synthesis is defined as a translation process from behavioral description into register-transfer-level (RTL) structural description.
The final goal of this translation process is to make the right tradeoffs among design targets (total area occupied, latency, performance or power consumption).

\vspace{1em} \noindent
The inputs to a typical HLS tool include a \textit{behavioral model}, a \textit{resource library} describing available hardware resources and a set of \textit{design constraints}:
\begin{itemize}
\item \textit{Behavioral description} specifies behavior in terms of operations,
assignment statements, and control constructs in a common high-level language
(e.g. C language);
\item \textit{Resource library} contains several alternatives
among which the synthesizer must select the one that best matches the design
constraints and maximizes the optimization objective;
\item \textit{Design constraints} can refer to the maximum number of available units of each resources, to the total area or to the latency of the specification execution.
\end{itemize}

\vspace{1em} \noindent
High-Level Synthesis involves three main tasks, the \emph{resource allocation and binding} (generation of the datapath) and the corresponding \emph{operation scheduling} and \emph{controller synthesis} (control unit definition):
\begin{itemize}
\item \emph{Resource allocation and binding} task is concerned with assigning operations and values to hardware components and then to interconnect them using connection elements. In detail, the process of datapath generation mainly consists of functional unit binding, register binding, and connection allocation steps.
\item \emph{Operation scheduling} determines the cycle-by-cycle behavior of a design by assigning parts of the computation to be performed to particular clock cycles (control steps or control states). In fact, scheduling provides the control steps in which operations start their execution.
\item \emph{Controller synthesis} provides the logic issue datapath operations, based on the control flow.
\end{itemize}
Solving the first two tasks efficiently is a non-trivial matter because of their NP-complete nature ~\cite{np_complete}.
Furthermore, the objectives are usually in contrast and the best high-level synthesis design flow cannot be known a priori since it depends on nature of the problem: the order in which the tasks are solved is extremely important and has a large impact on the final result.

\vspace{1em} \noindent
The outcome of a high-level synthesizer is both a structural view of the circuit, in particular of its \emph{datapath}, and a logic-level specification of its \emph{control unit}:
\begin{itemize}
\item \textit{Datapath} (at RTL level) is composed of functional units, storage and interconnection elements;
\item \textit{Controller} specifies every set of microoperations for the datapath to be performed during each control step.
\end{itemize}
High-Level Synthesis inputs and outputs are summarized in Figure \ref{fig:HLS}.
\begin{figure}[htb]
\centering
\includegraphics[height=0.6\columnwidth]{./chapters/hls/images/HLS.JPG}
\caption{HLS inputs and outputs}\label{fig:HLS}
\end{figure}

\section{Inputs}\label{hls:inputs}
High-Level Synthesis is concerned with the design and implementation of digital circuits starting from a \textit{behavioral description}, subject to a \textit{set of goals and constraints}, and given a \textit{library of different types of resources}.

\subsection{Behavioral Description}\label{hls:inputs:desc}
A \emph{behavioral description} is used as starting point for High-Level Synthesis. It specifies behavior in terms of operations, assignment statements, and control constructs in a hardware description language (HDL) (e.g.: VHDL or Verilog) or in a common software programming language (e.g.: C or Pascal). An HDL differs from a software programming language in its capability in expressing timing and concurrency in hardware.

\begin{figure}[bt!]
\centering
\begin{minipage}[l]{0.9\textwidth}
\begin{scriptsize}
\begin{verbatim}
void kim (int i1, int i2, int i3, int i4, int i5, int i6, int *o1,
          int *o2, const int c1, const int c2, const int c3,
          const int c4, const int c6, int C1, int C2) {

int a, e, m, n, p, u, i, b, f, g, q, r, c, h, j, s, t, w, d, k, l;

    if (C1) {
        if (C2) {
            a = i3 - i1;
            e = i2 + a;
            m = c3 + e;
            n = e - c2;
            p = a + c3;
            u = m + n;
            i = u + p;
        } else {
            b = i1 + i4;
            f = b - c2;
            g = c3 - b;
            q = f + c3;
            r = c2 + g;
            i = q + r;
        }
        *o1 = i + c6;
    } else {
        c = i1 - i5;
        h = c2 + c;
        j = c - c2;
        s = c3 + h;
        t = j - c3;
        w = t + c4;
        *o1 = s + w;
    }
    d = i6 + c1;
    k = c2 + d;
    l = d - c4;
    *o2 = k - l;
}

\end{verbatim}
\end{scriptsize}
\end{minipage}
  \caption{Example of Behavioral Description}\label{hls::code_example}
\end{figure}

\vspace{1em} \noindent
An example of behavioral description is the C code presented in Figure \ref{hls::code_example}; it is the Kim algorithm \cite{BIB::Kim} and it would be the reference behavioral description for every optimizations and examples performed during this thesis.

\vspace{1em} \noindent
Usually, to have a representation independent from the source code and easier to manage, the behavioral description is translated into an intermediate representation, as detailed in Section \ref{pre:IR}.

\subsection{Resource Library}\label{hls:inputs:lib}
The behavioral specification describes the input design of a high-level synthesis system. A system needs also information on which modules can be used during the synthesis. A collection of these modules is represented by a \textit{library}. It is common to use a set of modules each of which can only execute a limited set of operations.

\vspace{1em} \noindent
Modules implement different types of functions in hardware. They can be broadly
classified as follows:
\begin{itemize}
 \item \emph{Functional resources process data.} They implement arithmetic or logic functions
     and can be grouped into two subclasses:
\begin{itemize}
\item Primitive resources are subcircuits that are designed carefully once and used often. Examples are arithmetic units and some standard logic functions, such as encoders and decoders. Primitive resources can be stored in libraries. Each resource is fully characterized by its area and performance parameters.
\item Application-specific resources are subcircuits that solve a particular subtask. An example is a subcircuit servicing a particular function of a processor. In general such resources are the implementation of other HDL models. When synthesizing hierarchical sequencing graph models bottom up, the implementation of the entities at lower levels of the hierarchy can be viewed as resources.
\end{itemize}

\item \emph{Memory resources store data.} Examples are registers, read-only and read-write memory arrays. Requirements for storage resources are implicit in the graph model. In some cases, access to memory arrays is modeled as transfer of data across circuit ports.
\item \emph{Interface resources support data transfers.} Interface resources include busses that may he used as a major mean of communication inside a data path. External
interface resources are I/O pads and interfacing circuits.
\end{itemize}

\subsection{Design Constraints}\label{hls:inputs:constr}
A \emph{constraint} is a design target that must be met in order to consider the design
successful. For example, a chip may be required to run at a specific frequency in
order to interface with other components in a system.
Constraints in architectural synthesis can be classified into two major groups: \textit{interface
constraints} and \textit{implementation constraints}.

\begin{itemize}
  \item Interface constraints are additional specifications to ensure that the circuit can
be embedded in a given environment. They relate to the format and timing of the I/O
data transfers. The data format is often specified by the interface of the model. The
timing separation of I/O operations can be specified by timing constraints that can
ensure that a synchronous I/O operation follows/precedes another one by a defined
number of cycles in a given interval. Timing constraints can also specify data rates for pipelined systems.
  \item Implementation constraints reflect the desire of the designer to achieve a structure with some properties. Examples are area constraints and performance constraints, e.g., cycle-time and/or latency bounds.
\end{itemize}

\vspace{1em} \noindent
A different kind of implementation constraint is a \textit{resource binding constraint}.
In this case, a particular operation is required to be implemented by a given resource.
These constraints are motivated by the designer's previous knowledge, or intuition,
that one particular choice is the best and that other choices do not need investigation.
Architectural synthesis with resource binding constraints is often referred to as synthesis from partial structure. Design systems that support such a feature allow a designer to specify a circuit in a wide spectrum of ways, ranging from a full behavioral model to a structural one. This modeling capability may be useful to leverage previously designed components.

\vspace{1em} \noindent
For example, design constraints can be:
\begin{itemize}
\item $Area(x) \leq Area_{max}$; where $Area(x)$ is area occupied by the design solution
$x$ and $Area_{max}$ is the maximum allowed for total occupied area;
\item $Time(x) \leq Time_{max}$; where $Time(x)$ is latency of the solution $x$ and
$Time_{max}$ is maximum latency allowed to consider the solution admissible.
\end{itemize}
A solution that doesn't meet all design constraints is not considered feasible
and will have to be discarded, as shown in Figure \ref{fig:ex_constraints}.

\begin{figure}[htb]
\centering
\includegraphics[height=0.6\columnwidth]{./chapters/hls/images/ex_constraints.JPG}
\caption{Example of Design Constraints}\label{fig:ex_constraints}
\end{figure}


\section{Tasks}\label{hls:tasks}
Scheduling, allocation and binding, and controller synthesis are closely interdependent with one other: an optimal scheduling of operations to control steps without explicit performance and cost information of component allocation is impossible. Similarly, an optimal allocation of components cannot be performed without exact information on operation concurrency.

\vspace{1em} \noindent
Furthermore, there exist a performance/cost tradeoff by applying these tasks. For example, the most area efficient design consists of the minimum number of slow components such that a larger number of control steps is required to execute the desired function. On the other hand, allocating more components allows exploiting parallel executions of operations so that a higher performance can be achieved at the expense of higher area cost. By adjusting the constraints parameters, the design space can be explored. One primary application of HLS is in helping the designers with exploring the design space and hence multiple implementation alternatives quickly.

\subsection{Operation Scheduling}\label{hls:tasks:sched}
The scheduling problem is the problem of determining the order in which the operations in the behavioral description will be executed, as shown in Figure \ref{fig:ex_sched}.
\begin{figure}[htb]
\centering
\includegraphics[height=0.6\columnwidth]{./chapters/hls/images/ex_sched.JPG}
\caption{Example of Operation Scheduling}\label{fig:ex_sched}
\end{figure}
Within a control step, a separated functional unit is required to execute each operation assigned to that step. Thus, the total number of functional units required in a control step directly corresponds to the number of operations scheduled into it. If more operations are scheduled into each control step, more functional units are necessary, which results in fewer control steps for the design implementation. On the other hand, if fewer operations are scheduled into each control step, fewer functional units are sufficient, but more control steps are needed. Thus, scheduling determines the tradeoff between design cost and performance.

\subsection{Resource Allocation and Binding}\label{hls:tasks:RA}
After scheduling, a datapath can be constructed by two steps: \textit{unit allocation} and \textit{unit binding} (collectively called \textit{datapath allocation}).

\vspace{1em} \noindent
Unit allocation determines the number and types of resources to be used in the design. Since a real resource library may contain multiple types of functional units, each with different characteristics, unit allocation needs to determine the number and types of different functional and storage units from the component library.

\vspace{1em} \noindent
Unit binding maps the operations, variables, and data transfers on the scheduled intermediate representation into the functional, storage, and interconnection units, respectively, while ensuring that the design behavior operates correctly on the selected set of resources.

\vspace{1em} \noindent
The allocation of a datapath in high-level synthesis system consists basically of four dependent subproblems:
\begin{enumerate}
\item The \textit{storage value insertion} determines witch values have to be stored in registers;
\item The \textit{module allocation and binding} assigns modules to all operations;
\item The \textit{register allocation and binding} assigns registers to all values that have to be stored;
\item The \textit{interconnection allocation} connects all modules that are allocated in the previous steps.
\end{enumerate}

\subsection{Controller Synthesis}\label{hls:tasks:contr}
Controller synthesis is the last HLS task, in which the control flow is analyzed, the scheduling information is considered and, for each control step, the behavior of the system is defined. In particular, given the operations to be executed in a control step and the information about conditional evaluations, the controller will be able to define which operations have to be executed into each situation.

\section{Outputs}\label{hls:outputs}
High-Level Synthesis final output consists of two parts: a \emph{datapath stucture} at the register-transfer level (RTL), and a specification of the \emph{finite state machine} to control the datapath.

\subsection{Datapath}\label{hls:fsm}
The datapath describes a register transfer level design analogous to a schematic diagram. In particular, the datapath is described in terms of modules and their interconnections. An example of datapath is shown in Figure \ref{fig:ex_datapath}.
\begin{figure}[htb]
\centering
\includegraphics[height=0.6\columnwidth]{./chapters/hls/images/ex_datapath.JPG}
\caption{Example of Datapath}\label{fig:ex_datapath}
\end{figure}

\subsection{Controller}\label{hls:outputs:fsm}
The controller is defined as the part of the circuit that compute the evolution of the control flow, based on conditional inputs coming from the evaluation of the control constructs present in the initial specification.

\section{Objectives}\label{hls:obj}
The \textbf{design space} is the collection of all feasible structures corresponding to a circuit specification. The \textit{Pareto points} are those points of the design space that are not dominated by others in all objectives of interest. Hence they represent the spectrum of implementations of interest to designers. Their image determines the trade-off curves in the design evaluation space.

\vspace{1em} \noindent
Architectural exploration consists of traversing the design space and providing
a spectrum of feasible non-inferior solutions, among which a designer can pick the
desired implementation. Exploration requires the solution of constrained optimization
problems. Architectural synthesis tools can select an appropriate design point, according to some user-specified criterion, and construct the corresponding data path and control unit.

\vspace{1em} \noindent
Optimizing the High-Level Synthesis process means \emph{reduce the number of controller steps} and \emph{minimize the total area} occupied, always in accordance to design constraints (the number of available functional units).
This thesis aims to achieve these objectives by applying:
\begin{itemize}
  \item \emph{speculative scheduling}: in this way the size of the controller (number of states) decreases and the performance of the design increases, i.e. total delay decreases. In addition, the inherent parallelism in designs is extracted and resource utilization increases.
  \item \emph{optimal register allocation and binding}: in this way the number of required registers is reduced (although it is not necessary the minimum number) and their interconnection is minimized. In fact, sometimes the allocation of more registers leads to a reduction in the steering logic and thus to a reduction of the total area used.
\end{itemize}

\section{Conclusions}\label{hls:concl}
This Chapter has given an overview about High-Level Synthesis, introducing its inputs, tasks and outputs. It has presented the main objectives of this thesis, leaving open space to optimization analysis and implementation.
In next Chapter these basic information will be precisely defined and detailed; in particular, a layer of all necessary knowledge and preliminaries will be given.

